#include <iostream>
#include <vector>
#include <string>

using namespace std;


class ListNode {
public:
    int val;
    ListNode* next;

    ListNode(): val(0), next(nullptr) {}
    ListNode(int value): val(value), next(nullptr) {}
    ListNode(int value, ListNode* node_pointer): val(value), next(node_pointer) {}
};

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        return sortList(head, nullptr);
    }

    ListNode* sortList(ListNode* head, ListNode* tail) {
        if (head == nullptr) return head;
        if (head->next == tail) {
            head->next = nullptr;
            return head;
        };

        ListNode* slow = head;
        ListNode* fast = head;
        while (fast != tail) {
            slow = slow->next;
            fast = fast->next;
            if (fast != tail) {
                fast = fast->next;
            }
        }

        ListNode* mid= slow;

        return merge(sortList(head, mid), sortList(mid, tail));
    }
    
    ListNode* merge(ListNode* head1, ListNode* head2) {

        ListNode* dummy = new ListNode(0);
        ListNode* temp = dummy;
        ListNode* temp1 = head1;
        ListNode* temp2 = head2;

        while (temp1 != nullptr && temp2 != nullptr) {

            if (temp1->val <= temp2->val) {
                temp->next = temp1;
                temp1 = temp1->next;
            }
            else{
                temp->next = temp2;
                temp2 = temp2->next;
            }
            temp = temp->next;
        }
        if (temp1 != nullptr) {
            temp->next = temp1;
        }
        else if (temp2 != nullptr)
        {
            temp->next = temp2;
        }   
        return dummy->next;
    }
};